/**
 * 238. Product Of Array Except Self 除自身以外的数组乘积
 * https://leetcode-cn.com/problems/product-of-array-except-self/
 */
class ProductOfArrayExceptSelf {
    /**
     * 方法：使用前缀积和后缀积计算每个元素除自身外的乘积
     * 
     * Args:
     *     nums: 输入数组
     * 
     * Returns:
     *     返回一个数组，其中每个元素是输入数组除自身外所有元素的乘积
     * 
     * Time: O(n) - 只需要遍历数组两次
     * Space: O(1) - 除了输出数组外，只使用了常数空间
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] suf = new int[n];
        suf[n-1] = 1;
        for(int i = n - 2; i >= 0; i--){
            suf[i] = suf[i+1] * nums[i+1];
        }
        int pre = 1;
        for(int i = 0; i< n; i++){
            suf[i] *= pre;
            pre *= nums[i];
        }
        return suf;
    }
}